#ifndef BPLUSTREE_H
#define BPLUSTREE_H

#include <assert.h>
#include <string>
#include <vector>


#define ORDER (BLOCK_LENGTH/8-1)
using namespace std;

int iDebugON=0;

struct indexinfo {
	char iname[FILE_NAME_LENGTH];
	int offset;
	int dups;
	int root_block;
	int block_count;

};

class bplustree
{
private:
    
	stm*	st1;
	buffer* bufmgr;

public:
	bplustree(buffer *buf1, indexinfo *iinfo);
	~bplustree();

	int  insertInMemory(int *aRow, int aTableBlocckNo);
	int commit();
	void printIndex();
	void printBuffer(int* aBuffer);
	vector<int>  getTableBloks (int aKey, int aDebugOn );
	void insert(int* aBuffer, int aKey, int aPointer);
	int getIndexBlockID(int* aBuffer, int aKey) ;
	int getTableBlockID(int* aBuffer, int aKey) ;
	void insertPointerInBucket(int aBucketPointer, int aPointer);
	block* splitBufferAndReturnKey(int* aBuffer, int aAppendKey, int aAppendPointer);
	void bufferUpdateKey(int* aBuffer, int aOldKey, int aNewKey);
	bool debug;
	
	char iname[FILE_NAME_LENGTH];
	int  attrib_id;
	int  num_blocks;
	int  dups;
	int  num_attribs;
	int  num_records;
	int  mRootBlockNo;

};


bplustree :: bplustree(buffer * buf1, indexinfo *iinfo)
{

	strcpy(iname, iinfo->iname);
	attrib_id   = iinfo->offset;
	dups  = iinfo->dups;
	num_blocks  = iinfo->block_count;
	mRootBlockNo = iinfo->root_block;
	
	st1 	= new stm(iname);
	bufmgr = new buffer(4);

	// CONSTANTS 
	num_attribs = 2;
	num_records = ORDER;

	if(iDebugON)	cout << "Intialization for index " << iinfo->iname << endl;
	if(iDebugON)	printIndex();
}


bplustree :: ~bplustree()
{
	delete bufmgr;
	delete st1;
}


int bplustree :: insertInMemory(int *aRow, int aTableBlocckNo)
{

	int lLastElement;
	int Myvalue = aRow[attrib_id];
	int i;
	int found;
	int foundLeaf;
	int parentBlockID;
	int newBlockNumber = mRootBlockNo;
	int oldBlockNumber;
	block* currIdxBlock;
	block* siblingBlock;
	block* parentBlock;
	foundLeaf = 0;
	vector<int> parents;
	int oldPArentKey;
	vector<int> tableBloks;

	if(iDebugON)	PRINT("\nIndex %s on attrib_id=%d\n", iname, attrib_id);
	if(iDebugON)	PRINT("(k,p) = (%d, %d)\n", Myvalue, aTableBlocckNo);
	if(iDebugON)	PRINT("number of blocks: %d\n", num_blocks);

	if (num_blocks == 0 ) {
	// get root
		if(bufmgr->get_new_block(iname, newBlockNumber,&currIdxBlock)) { }
		else
		{
			currIdxBlock->initialize(iname, 2, newBlockNumber, 0, st1);
			currIdxBlock->buffer[11] = 0;
			num_blocks ++;
		}
	} 
	else 
	{
		// get root
		bufmgr->get_block_num( iname, newBlockNumber, &currIdxBlock);
		currIdxBlock->initialize(iname, 2, newBlockNumber, 6, st1);

		if (currIdxBlock->buffer[11] < 0) { parents.push_back( newBlockNumber );}
	}

	if(iDebugON) 
	{
		PRINT("---------------------------------------------\n");
		printBuffer(currIdxBlock->buffer);
		PRINT("---------------------------------------------\n");
	}

	while (currIdxBlock->buffer[11] < 0) { 
		if(iDebugON) 	printBuffer(currIdxBlock->buffer);
		newBlockNumber = getIndexBlockID(currIdxBlock->buffer, Myvalue);
		bufmgr->get_block_num( iname, newBlockNumber, &currIdxBlock);
		currIdxBlock->initialize(iname, 2, newBlockNumber, 6, st1);

		if (currIdxBlock->buffer[11] < 0)  { parents.push_back( newBlockNumber );}
	} // found leaf

	//currIdxBlock is the right leaf to add value
	if (abs(currIdxBlock->buffer[11])  <  5) {
		//add value here
		if(iDebugON) 
		{
			PRINT("Inserting in block:%d\n", newBlockNumber);
	        	printBuffer(currIdxBlock->buffer); 
		}
	        oldPArentKey = currIdxBlock->buffer[1];  
	        insert( currIdxBlock->buffer, Myvalue, aTableBlocckNo);
        	if ((parents.size() > 0 )){
			bufmgr->get_block_num( iname, parents[parents.size() - 1], &parentBlock);
			parentBlock->initialize(iname, 2, parents[parents.size()-1], 6, st1);

			bufferUpdateKey(parentBlock->buffer, oldPArentKey, currIdxBlock->buffer[1]);
			if(iDebugON) 
			{
				cout << "Parent Modified: " ;
				printBuffer(parentBlock->buffer); 
			}
		}
	} 
	else 
	{ // this bucket is full so we'll have to do a split
		int finished = 0;
		if(iDebugON) 
		{
			cout << "Full Block: "<< newBlockNumber<< " Tail: " << currIdxBlock->buffer[11] << endl;
			cout << "Will split" << endl;
			cout << "Before split: " ;
			printBuffer(currIdxBlock->buffer); 
		}
		newBlockNumber = aTableBlocckNo;
                while ((finished == 0) ) {
			oldPArentKey = currIdxBlock->buffer[1];
                        oldBlockNumber = newBlockNumber;
			if(iDebugON) 
			{
				PRINT("Before split: "); 
				printBuffer(currIdxBlock->buffer); 
				PRINT("Block Number being inserted is %d\n", oldBlockNumber);
			}
                        siblingBlock = splitBufferAndReturnKey(currIdxBlock->buffer, Myvalue, oldBlockNumber);
			oldBlockNumber = currIdxBlock->get_block_no(); //MBM
			newBlockNumber = num_blocks -1; 
			if(iDebugON)	PRINT("siblingBlock %d, num_blocks-1=%d\n", siblingBlock->get_block_no(), num_blocks-1);

			if(iDebugON) 
			{
				PRINT("After split and Insert: \n");
				PRINT("newBlock:%d, oldBlock: %d\n", newBlockNumber, oldBlockNumber);
				PRINT("The block that got splitted is \n");
				printBuffer(currIdxBlock->buffer); 
				PRINT("The new block that got created is \n");
                        	printBuffer(siblingBlock->buffer);
			}
                        Myvalue = siblingBlock->buffer[10]; //temporary save Myvalue - when spliting internal nodes key is lost from buffer
			
                        if (parents.size() > 0) {
				parentBlockID = parents[parents.size()-1];
                                parents.pop_back();
				if(iDebugON) 
				{
					cout << "Have to insert this new key=" << Myvalue<< " pointer=" << newBlockNumber <<" into parent"<<endl;
				}
                                bufmgr->get_block_num(iname, parentBlockID, &parentBlock);
				parentBlock->initialize(iname, 2, parentBlockID, 6, st1);

                                bufferUpdateKey(parentBlock->buffer, oldPArentKey, currIdxBlock->buffer[1]);
				if (iDebugON)
				{
					PRINT("Parent block for splitted block is \n");
					printBuffer( parentBlock->buffer);
				}
                                if (abs(parentBlock->buffer[11]) < 5 ) {
	                                insert( parentBlock->buffer, Myvalue, newBlockNumber);
					if(iDebugON) 
					{
						cout << "Updated parent: ";
                                        	printBuffer( parentBlock->buffer);
					}
	                                finished = 1;
				} else {
	                                // block to split = 
                                        // value to insert = 
                                        // pointer to insert = 
                                        currIdxBlock = parentBlock;
                                }
			} 
			else  
                        {
                                if(bufmgr->get_new_block(iname, num_blocks, &currIdxBlock)){ }
				currIdxBlock->initialize(iname, 2, num_blocks, 0, st1);
                                num_blocks++;
				//cout<<"******************************************\n";
				//cout<<"oldBlockNo:" <<oldBlockNumber<<endl;
				//cout<<"Myvalue:" <<Myvalue;
				//cout<<"newBlockNo:"<<newBlockNumber;
				//cout<<"**************** after splitting **************\n";
                                currIdxBlock->buffer[0] = oldBlockNumber;
                                currIdxBlock->buffer[1] = Myvalue;
                                currIdxBlock->buffer[2] = newBlockNumber;
				currIdxBlock->buffer[11] = -1;
                                mRootBlockNo = num_blocks -1;
				if(iDebugON) 
				{
					cout<< "New Root:";
                               		printBuffer( currIdxBlock->buffer ) ;
				}
                                finished = 1;
			}
		} // while
	} // else bucket full
	if (iDebugON)
	{
		cout<<"current block:";
		printBuffer(currIdxBlock->buffer);
	}
        return 0;
}

void bplustree::printBuffer(int* aBuffer) {

	if (aBuffer[9] == 1234321) 
	{
		cout << "Pointer bucket of length " << aBuffer[11]<<": ";
		for (int i=0;i<aBuffer[11];i++) 
		{
			cout << aBuffer[i] <<" ";
		}
		cout << " Next overflow bucket: "<< aBuffer[10] << endl;
	} 
	else if (aBuffer[11] >= 0) 
	{
		cout << "Leaf Node of length " << aBuffer[11]<<": ";
		for (int i=0;i<aBuffer[11];i++) 
		{
			cout << "("<< aBuffer[2*i] <<","<< aBuffer[2*i + 1] << ") ";
		}
		cout << endl;
	} 
	else 
	{
		cout << "Internal Node of length " << -aBuffer[11]<<": ";
		for (int i=0;i<-aBuffer[11];i++) 
		{
			cout << " p"<< aBuffer[2*i] <<" k"<< aBuffer[2*i + 1];
		}
		cout << " p"<< aBuffer[-aBuffer[11]*2] << endl;
	}
	cout << "Number of keys in the buffer:" << aBuffer[11]<<endl;
}


int bplustree  :: commit(){

	bufmgr->commit();
	st1->flush();
	return 0;
}

void bplustree :: bufferUpdateKey(int* aBuffer, int aOldKey, int aNewKey) 
{

	//MBM: this can be removed ...
	if(iDebugON)	PRINT("OldKey %d, NewKey %d\n", aOldKey, aNewKey);

	for (int i = 0; i< abs(aBuffer[11]); i++) 
	{
		if (aBuffer[2*i+1] == aOldKey)
		{
			aBuffer[2*i+1] = aNewKey;
		}
  	}
}

void bplustree :: insert(int* aBuffer, int aKey, int aPointer) {
	int lLastPair =  abs(aBuffer[11]);
	int i = 0;
	int found = 0;
        int offset = 0;
	int updateTailCounter = 1;
	   
	if (aBuffer[11] < 0) 
	{
		offset = 1; 
	}
	while ((found != 1) && (i<lLastPair)) 
	{
		if (aKey <= aBuffer[2*i + 1])
		{
			found = 1;
			updateTailCounter = (aKey < aBuffer[2*i + 1])? 1:0;
			if ((offset == 0) && (aKey == aBuffer[2*i + 1]) && (aBuffer[2*i] >= 0) && (aPointer != aBuffer[2*i])) 
			{
				//create new bucket
				block* bucket;
				if(bufmgr->get_new_block(iname, num_blocks, &bucket)){}
				bucket->initialize(iname, 2, num_blocks, 0, st1);
				num_blocks++;
				bucket->buffer[0] = aBuffer[2*i];
				bucket->buffer[1] = aPointer;
				aBuffer[2*i] = -(num_blocks - 1);
				bucket->buffer[11] = 2;
				bucket->buffer[10] = -1;
				bucket->buffer[9] = 1234321;
				updateTailCounter = 0;
				//add this pointer and new pointer in a new bucket
				// make aBuffer[2*i] negative and pointing to the bucket
			} 
			else if ((offset == 0) && (aKey == aBuffer[2*i + 1]) && (aBuffer[2*i] < 0 )) 
			{
				// add the new pointer to the bucket or extend bucket
				insertPointerInBucket(-aBuffer[2*i], aPointer); 
				updateTailCounter = 0;
			} 
			else if (aKey < aBuffer[2*i + 1]) 
			{
				for (int j=lLastPair*2; j>=2*i; j--) 
				{
					aBuffer[j+2+offset] = aBuffer[j+offset];
				}
				aBuffer[2*i+1] = aKey;
				if (offset == 0) 
				{
					aBuffer[2*i] = aPointer;
				} 
				else 
				{
					aBuffer[2*i+2] = aPointer;
				}
			}
		}
		else 
		{
			i++;
		}
	} // while
	if ((found == 0) && (lLastPair == i )) 
	{
		aBuffer[2*i+1] = aKey;
		if (offset == 0) 
		{
			aBuffer[2*i] = aPointer;
		}
		else 
		{
			aBuffer[2*i+2] = aPointer;
		}
	}
	if (updateTailCounter == 1) 
	{
		if (aBuffer[11] >= 0) 
		{
			aBuffer[11] = aBuffer[11] + 1;
		} 
		else 
		{
			aBuffer[11] = aBuffer[11] - 1;
		}
	} 
}

void bplustree :: insertPointerInBucket(int aBucketPointer, int aPointer) {
	int i;
	int found = 0;
	int hasMore = 0;
	block* bucket;

	if(bufmgr->get_block_num( iname, aBucketPointer,&bucket)){}
	bucket->initialize(iname, 2, aBucketPointer, 6, st1);

	do {
		hasMore = 0;
		for (i=0; i< bucket->buffer[11]; i++) 
		{
			if (aPointer == bucket->buffer[i]) 
			{
				found = 1;
			}
		}
		if ((found == 0) && (bucket->buffer[10]>0)) 
		{ 
			int id = bucket->buffer[10];
			if(bufmgr->get_block_num(iname, id,&bucket)) {}
			bucket->initialize(iname, 2, id, 6, st1);
			hasMore = 1;
		}
	}while ((found == 0) && (hasMore == 1));
	
	if (found == 0) 
	{
		if (bucket->buffer[11]  < 8) 
		{
			bucket->buffer[bucket->buffer[11]] = aPointer; 
			bucket->buffer[11] = bucket->buffer[11] + 1;
		}
		else 
		{
			block* bucket2;
			if(bufmgr->get_new_block( iname, num_blocks, &bucket2)) {}
			bucket2->initialize(iname, 2, num_blocks, 0, st1);
			num_blocks++;
		        bucket->buffer[10] = num_blocks -1;
			bucket2->buffer[0] = aPointer;
			bucket2->buffer[11] = 1;
			bucket2->buffer[10] = -1;
			bucket2->buffer[9] = 1234321;
		}
	}
}

int bplustree :: getIndexBlockID(int* aBuffer, int aKey) {
	int lLastPair =  abs(aBuffer[11]);
	int i = 0;
	int found = 0;
	int aPointer;
	
	while ((found == 0) && (i<lLastPair)) 
	{
		if (aKey < aBuffer[2*i + 1])
		{
			found = 1;
			aPointer = aBuffer[2*i];
		}
		else
		{
			aPointer = aBuffer[2*i + 2];
			i++;
		}
	} // while
	return aPointer;
}

int bplustree :: getTableBlockID(int* aBuffer, int aKey) {
	int lLastPair =  abs(aBuffer[11]);
	int i = 0;
	int found = 0;
	int aPointer = -1000000; // not found

	while ((found == 0) && (i<lLastPair)) 
	{
		if (aKey == aBuffer[2*i + 1])
		{
			found = 1;
			aPointer = aBuffer[2*i];
		}
		else 
		{
			i++;
		}
	} // while
	return aPointer;
}



block* bplustree :: splitBufferAndReturnKey(int* aBuffer, int aAppendKey, int aAppendPointer) {
	int isLeaf = (aBuffer[11] >= 0);
	int splitPoint;
	int splitGroup;
	int offset = 0;

	if (aAppendKey < aBuffer[5]) 
	{
		splitPoint=2;
		splitGroup = 0;
	} 
	else 
	{
		splitPoint=3; 
		splitGroup = 1;
	}
	
	if (!isLeaf) 
	{
		splitPoint = 2; 
		offset = 2;
	}
	
	block* currIdxBlock;
	if(bufmgr->get_new_block( iname, num_blocks, &currIdxBlock)) {} // get root
	currIdxBlock->initialize(iname, 2, num_blocks, 0, st1);
	num_blocks++;
	for (int i=0;i<(5-splitPoint)*2;i++) 
	{
		currIdxBlock->buffer[i] = aBuffer[i+splitPoint*2 + offset];
  	}
	if (aBuffer[11] > 0) 
   	{
		aBuffer[11] = splitPoint; 
		currIdxBlock->buffer[11] = 5 - splitPoint ; 
		currIdxBlock->buffer[10] = currIdxBlock->buffer[1];
	} 
	else
	{
		aBuffer[11] = -splitPoint; 
		currIdxBlock->buffer[11] = -2; 
		currIdxBlock->buffer[10] = aBuffer[5];
	}
	if (splitGroup == 0) 
	{
		insert(aBuffer, aAppendKey, aAppendPointer);
	} 
	else 
	{
		insert(currIdxBlock->buffer, aAppendKey, aAppendPointer);
	}
	return currIdxBlock;
}

void bplustree :: printIndex() 
{
	block* blk;

	SHEAD("Block Count: %d\n", num_blocks);
	SHEAD("Root BlockNum: %d\n", mRootBlockNo);

	for (int i=0; i< num_blocks; i++) 
	{
		if(bufmgr->get_block_num( iname, i, &blk)) {}
		blk->initialize(iname, 2, i, 6, st1);
		printBuffer( blk->buffer); 
	}
}

vector<int> bplustree :: getTableBloks (int aKey, int aDebugOn ) 
{
	vector<int> r;

	if(iDebugON)	PRINT("\nSearch Key is %d\n", aKey);
	if(iDebugON)	cout<<"mRootBlockNo in getTableBloks:" << mRootBlockNo<<endl;

	if (num_blocks > 0 ) 
	{
		block* idxBlock;
		int blockID = mRootBlockNo;
		int fnd1 = 0;
		int fnd2 = 0;
		int cnt = 0;
		int nextBucket;

		if(bufmgr->get_block_num (iname, blockID, &idxBlock)) {}
		idxBlock->initialize(iname, 2, blockID, 6, st1);
		if (iDebugON) 
		{
			cout << "Get Root block("<< blockID<<") of index: ";
			printBuffer( idxBlock->buffer ); 
		}
		while (fnd1 == 0) 
		{
			if (idxBlock->buffer[11] < 0 ) 
			{
				blockID = getIndexBlockID(idxBlock->buffer, aKey) ;
				if(bufmgr->get_block_num(iname, blockID, &idxBlock)) {}
				idxBlock->initialize(iname, 2, blockID, 6, st1);
				if (iDebugON) 
				{
					cout << "Get Block " << blockID << " of index : ";
					printBuffer( idxBlock->buffer ); 
				}
			} 
			else 
			{
				if (iDebugON) 
				{
					cout << "Found the leaf node"<<endl;
				}
				int tblID =  getTableBlockID(idxBlock->buffer, aKey);
				if (tblID>=0) 
				{
					if (iDebugON) 
					{
						cout << "Leaf node points directly to table block: "<< tblID <<endl;
					}
					r.push_back( tblID);
					fnd1=1;
				} 
				else if (tblID == -1000000) 
				{
					fnd1=1;
				}
				else
				{
					fnd1=1;
					cnt=1;
					if (iDebugON) 
					{
						cout << "Leaf node points to Pointer Bucket node: "<< -tblID <<endl;
					}
					while (cnt == 1) 
					{ 
						if(bufmgr->get_block_num( iname, -tblID,&idxBlock )) {}
						idxBlock->initialize(iname, 2, -tblID, 6, st1);
						if (iDebugON) 
						{
							cout << "Get Pointer Bucket " << -tblID << " : ";
							printBuffer( idxBlock->buffer ); 
						}
						for (int j=0;j<idxBlock->buffer[11];j++) 
						{ 
							r.push_back( idxBlock->buffer[j]);
						}
  						if ((idxBlock->buffer[11] == 8) && (idxBlock->buffer[10] > 0)) 
						{
							tblID = -idxBlock->buffer[10];
							cnt = 1;
  						} 
						else 
						{
							cnt=0;
						}
					} // while
				}
			}
		}
	}

	return r;
}


/*
bool CindexEntry::operator== (string aIndexName) const
{
   return mIndexName == aIndexName;
}
*/

#endif
